#include <stdlib.h>
#include <math.h>

int sedgewick(int n){
	if(n%2==0){
		return 9*(pow(4,n/2)-pow(2,n/2))+1;
	}else{
		return pow(4,(n+3)/2)-3*pow(2,(n+3)/2)+1;
	}
}

void ShellSort(int array[],int n){
	int si=0;
	while(sedgewick(++si)<n/2);
	int d;
	int p,i,temp;
	while(--si>=0){
		d=sedgewick(si);
		for(p=d;p<n;p++){
			temp=array[p];
			for(i=p;i>0&&array[i-d]>temp;i-=d){
				array[i]=array[i-d];
			}
			array[i]=temp;
		}
	}
}
